Day15 Leetcode Array系列---- Min Cost Climbing Stairs

本次題目 Min Cost Climbing Stairs by JS

這一次題目是爬樓梯，在這個樓梯可以選擇從第 0 階或第 1 階開始走，一次可以選擇跨 1 格或跨 2 格，踩上每一階梯都會消耗該階梯對應的體力，在走完樓梯的時候希望得到最小的體力消耗

cost1 = [10, 15, 20]
output1 = 15

cost2 = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
output2 = 6

思考路線

1. 需要用 while 迴圈，因為不確定第幾圈會走到樓梯頂端
2. 我會需要指針，紀錄我每一圈踩在第幾階梯
3. 需要紀錄踩到階梯的體力花費
4. 先考慮什麼狀況要走 1 格，什麼狀況走 2 格
5. 當第 1 格比第 2 格小的時候走 1 格，反之走 2 格
6. 指針會隨著走的格數改變
7. 仔細觀察後發現，一定會走過的區塊是從索引 1 開始
8. 所以我們要考慮什麼狀況會走第 0 階與第 1 階
9. 我們可以把起始從第 0 階或第 1 階都拿去計算，最後取最小值
10. 如果從第 1 階開始走就要考慮會不會與 while 迴圈的加總重複計算

Coding Time by 大大

先從判斷往前走 1 格還是走 2 格開始寫，如果往前 1 格的體力花費比往前 2 格小，就走 1 格，這個時候 index + 1 ，反之走 2 格 index + 2，再把體力消耗加總

因為我比較的項目是 ary[index+1] 有可能會超出陣列長度，所以可以用 a = a || 2 這種概念，超出長度會回傳 undefine ，如果是 undefine 我就給它 0

function lowestCost (ary){
  index = 0
  total = 0 
  while(index < ary.length){ 
    if( ary[index] < ary[index+1] ){
      total += ary[index]
      index += 1  
    }else{
      total += (ary[index+1] || 0)
      index += 2
    }
  }
}
function expect(a,b){
    console.log( a == b )
}
expect(lowestCost(cost1),output1)
expect(lowestCost(cost2),output2)

一定會走過的區塊是從索引 1 開始，所以我可以把迴圈加總結果與從第 0 階開始或第 2 階開始相加，取最小值，這樣就能找出最省體力的走法

考慮到從第 1 階開始走會與 while 迴圈重複計算，所以當我從第 1 階開始走我就把它的體力花費指派為 0 ，讓迴圈去加這個體力消耗

function lowestCost (ary){
  a = ary[0]

  if(ary[1] < ary[2]){
    b = 0
  }else{
    b = ary[1]
  }

  index = 1
  total = 0 
  while(index < ary.length){ 
    if( ary[index] < ary[index+1] ){
      total += ary[index]
      index += 1  
    }else{
      total += (ary[index+1] || 0)
      index += 2
    }
  }
  return Math.min(a+total,b+total)
}
function expect(a,b){
    console.log( a == b )
}
expect(lowestCost(cost1),output1)
expect(lowestCost(cost2),output2)

最後用 min 找體力消耗最小值

Coding Time by 大大 with Ruby

大大除了用 while 迴圈解決這題也想出了遞迴的方式

當 ary 存在且 a b 等於 nil ，就把 ary 第 1 個元素拔出來指派給 a ， 指派 a 後，設定 b 的時候，就要考慮現在 index 0 1 兩個索引在陣列取出的值誰大誰小，如果 ary[0] < ary [1] 我就把 0 指派給 b ，這代表現在陣列 a[0] 的位置之後會踩到，反之指派 ary[0] 給 b

接著判斷走 1 格踩到的體力消耗小還是走 2 格體力消耗小，在拔掉對應數量的元素，最後當陣列長度等於 0 ，代表走到階梯的頂端

def min_cost(ary, a = nil, b = nil, total = 0)
  if ary.size == 0
    [a + total, b + total].min
  elsif ary && a.nil? && b.nil?
    a = ary.shift
    b = ary[0] < ary[1].to_i ? 0 : ary[0]
    min_cost(ary, a, b, total)
  else
    if ary[0] < ary[1].to_i
      total += ary[0]
    else
      total += ary[1].to_i
      ary.shift
    end
    ary.shift
    min_cost(ary, a, b, total)
  end
end

結論

SOR 這題我是靠大大，我很快的做到 while 迴圈，但是一直卡在要從第 0 階或第 1 階開始走，大大的方法是先計算這兩種走法共同區塊，最後用 min 判斷會從哪開始

今天到此為止，有任何問題請在下方留言或透過email、GitHub聯絡我，感謝閱讀

Daily kitty